#include <stdio.h>
#include "mainCuda.h"
#include "main.h"
#include "plane.h"

#define US unsigned short
__global__
void movePoints(US *m, US *k, US *f, US *b, Point *fixedPoints, Point *variablePoints, Possibility *possibilities, int *moved, int *candidates);
__device__
Point getDiff(int index);
__device__
int hasFixedPoint(Point point, int f, Point *fixPoints);
__device__
float countDistance(Point point1, Point point2);
__device__
int pointsEqual(Point point1, Point point2);
__device__
void bubbleSort(Possibility *array, int length);

/*
 * Pracovní metoda programu s hlavním cyklem, který má na zodpovědnost zpracovat
 * všechny stavy. Po skončení vypíše nejlepší řešení.
 */
void doWork(void) {
	int i;
	int moved = 0, *moved_d;
	int *candidates_d;
	US *m_d, *k_d, *f_d, *b_d;
	Point *fixedPoints_d;
	Point *variablePoints_d;
	Possibility *possibilities_d;
	/* m */
	cudaMalloc(&m_d, sizeof(unsigned short));
	cudaMemcpy(m_d, &m, sizeof(unsigned short), cudaMemcpyHostToDevice);
	/* k */
	cudaMalloc(&k_d, sizeof(unsigned short));
	cudaMemcpy(k_d, &k, sizeof(unsigned short), cudaMemcpyHostToDevice);
	/* f */
	cudaMalloc(&f_d, sizeof(unsigned short));
	cudaMemcpy(f_d, &f, sizeof(unsigned short), cudaMemcpyHostToDevice);
	/* b */
	cudaMalloc(&b_d, sizeof(unsigned short));
	cudaMemcpy(b_d, &b, sizeof(unsigned short), cudaMemcpyHostToDevice);
	/* pevné body */
	cudaMalloc(&fixedPoints_d, f * sizeof(Point));
	cudaMemcpy(fixedPoints_d, fixedPoints, f * sizeof(Point), cudaMemcpyHostToDevice);
	/* variabilní body */
	cudaMalloc(&variablePoints_d, (b - f) * sizeof(Point));
	cudaMemcpy(variablePoints_d, variablePoints, (b - f) * sizeof(Point), cudaMemcpyHostToDevice);
	/* alokace pro possibilities */
	cudaMalloc(&possibilities_d, (b - f) * 9 * sizeof(Possibility));
	cudaMalloc(&candidates_d, (b - f)*sizeof(int));
	cudaMalloc(&moved_d, sizeof(int));
	/* Počítáme, dokud se některý bod pohnul */
	do{
		cudaMemset(moved_d, 0, sizeof(int));
		movePoints<<<1, (b - f)>>>(m_d, k_d, f_d, b_d, fixedPoints_d, variablePoints_d, possibilities_d, moved_d, candidates_d);
		cudaThreadSynchronize();
		cudaMemcpy(&moved, moved_d, sizeof(int), cudaMemcpyDeviceToHost);
		/*cudaMemcpy(candidates, candidates_d, (b - f) * sizeof(int), cudaMemcpyDeviceToHost);
		for(i = 0; i < (b - f); i++){
			cudaMemcpy(possibilities[i], &(possibilities_d[9 * i]), 9 * sizeof(Possibility), cudaMemcpyDeviceToHost);
			printPossibilities(i);
		}
		printf("Candidates:\n[");
		for(i = 0; i < (b - f); i++){
			printf("%d, ", candidates[i]);
		}
		printf("]\n");
		cudaMemcpy(variablePoints, variablePoints_d, (b - f) * sizeof(Point), cudaMemcpyDeviceToHost);
		printPlane();*/
	}while(moved);
	cudaMemcpy(variablePoints, variablePoints_d, (b - f) * sizeof(Point), cudaMemcpyDeviceToHost);

	cudaFree(m_d);
	cudaFree(k_d);
	cudaFree(f_d);
	cudaFree(b_d);
	cudaFree(fixedPoints_d);
	cudaFree(variablePoints_d);
	cudaFree(possibilities_d);
	cudaFree(candidates_d);
	cudaFree(moved_d);
}

/**
 * Pro všechny stavy spočítá možnosti jejich přesunu.
 */
__global__
void movePoints(US *m, US *k, US *f, US *b, Point *fixedPoints, Point *variablePoints, Possibility *possibilities, int *moved, int *candidates){
	int i = threadIdx.x;
	int offset = i * 9;
	int j, l;
	float res;
	Point current = variablePoints[i], possibility, best;
	int hasConflict;

	for(j = 0; j < 9; j++){
		res = 0;
		possibility.x = current.x + getDiff(j).x;
		possibility.y = current.y + getDiff(j).y;
		if(possibility.x < 0 || possibility.x >= *m || possibility.y < 0 || possibility.y >= *k){
			res = -3;
		}
		if(hasFixedPoint(possibility, *f, fixedPoints)){
			res = -2;
		}
		if(res >= 0){
			for(l = 0; l < *f; l++){
				res += countDistance(fixedPoints[l], possibility);
			}
			for(l = 0; l < (*b - *f) - 1; l++){
				if(l != i){
					res += countDistance(variablePoints[l], possibility);
				}
			}
		}
		possibilities[offset + j].point = possibility;
		possibilities[offset + j].value = res;
	}
	bubbleSort(&(possibilities[offset]), 9);

	__syncthreads();

	candidates[i] = 0;
	if(i == 0){
		do{
			hasConflict = 0;
			for(j = 0; j < (*b - *f) - 1; j++){
				for(l = j + 1; l < (*b - *f); l++){
					if(pointsEqual(possibilities[j * 9 + candidates[j]].point, possibilities[l * 9 + candidates[l]].point)){
						if(pointsEqual(possibilities[j * 9 + candidates[j]].point, variablePoints[j])){
							candidates[l]++;
						}
						else{
							candidates[j]++;
						}
						hasConflict = 1;
						break;
					}
				}
				if(hasConflict){
					break;
				}
			}
		}while(hasConflict);
	}

	__syncthreads();

	best.x = possibilities[offset + candidates[i]].point.x;
	best.y = possibilities[offset + candidates[i]].point.y;
	if(!(pointsEqual(variablePoints[i], best))){
		*moved = 1;
	}

	variablePoints[i] = best;
}

/*
 * Metoda vrátí změnu souřadnic v závislosti na indexu, viz:
 *    |-1| 0| 1|
 *  --+--+--+--+
 *  -1| 0| 1| 2|
 *  --+--+--+--+
 *   0| 3| 4| 5|
 *  --+--+--+--+
 *   1| 6| 7| 8|
 *  --+--+--+--+
 *  Tj. např. pro "5" vrátí [0, 1].
 *  Používá se pro počítání souřadnic okolí bodu.
 */
__device__
Point getDiff(int index){
	Point p;
	switch(index){
	case 0: case 1: case 2:
		p.x = - 1;
		break;
	case 3: case 4: case 5:
		p.x = 0;
		break;
	case 6: case 7: case 8:
		p.x = 1;
	}
	switch(index){
	case 0: case 3: case 6:
		p.y = -1;
		break;
	case 1: case 4: case 7:
		p.y = 0;
		break;
	case 2: case 5: case 8:
		p.y = 1;
	}
	return p;
}

/*
 * Vrátí TRUE, pokud je na zadaném bodu pevně umístěný bod.
 */
__device__
int hasFixedPoint(Point point, int f, Point *fixPoints){
	int i, res = 0;
	for(i = 0; i < f; i++){
		if(pointsEqual(point, fixPoints[i])){
			res = 1;
			break;
		}
	}
	return res;
}

/*
 * Spočítá euklidovskou vzdálenost dvou bodů pomocí pythagorovy věty.
 */
__device__
float countDistance(Point point1, Point point2){
	int resX = point1.x - point2.x;
	int resY = point1.y - point2.y;

	return sqrt((float)((resX*resX) + (resY*resY)));
}

/*
 * Vrátí, zda-li se zadané body rovnají v souřadnicích.
 */
__device__
int pointsEqual(Point point1, Point point2){
	return point1.x == point2.x && point1.y == point2.y;
}

/**
 * Implementace bubble sortu pro pole struktur možností.
 * Pole nikdy nebude delší než 9 prvků, bubble sort zvolen pro malý kód a
 * paměťovou nenáročnost.
 */
__device__
void bubbleSort(Possibility *array, int length){
	int i, j;
	Possibility temp;
	for(i = length - 1; i > 0; i--){
		for(j = 0; j < i; j++){
			if(array[j].value < array[j+1].value)
			{
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
			}
		}
	}
}

